package offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Elephas
 * @Date 2022/1/19
 **/
public class RecoverTree {

    /*
        解法一： 由于所给二叉树是 交换了两个节点值后是平衡二叉树，因此其交换后中序序列是递增的。
        由此性质，如果交换两个节点不相邻，则必定会出现两个极值，如果相邻，会出现一个极值。
        因此遍历过程中如果找到两个极值将他们交换，如果找到一个极值则交换极值相邻元素
     */
    public void recoverTree(TreeNode root){
        List<TreeNode> treeNodeList = new ArrayList<>();
        recoverTreeHelper(treeNodeList,root);
        TreeNode node1 = null,node2 = null;
        boolean swapped = false;
        if(treeNodeList.isEmpty()){
            return;
        }else{
            TreeNode pre = treeNodeList.get(0);
            for (int i = 1; i < treeNodeList.size(); i++) {
                if(node1 == null && pre.val > treeNodeList.get(i).val){
                    node1 = pre;
                    node2 = treeNodeList.get(i);
                }else if(node1 != null && pre.val > treeNodeList.get(i).val){
                    node2 = treeNodeList.get(i);
                    int temp = node1.val;
                    node1.val = node2.val;
                    node2.val = temp;
                    swapped = true;
                }
                pre = treeNodeList.get(i);
            }
            if(!swapped){
                int temp = node1.val;
                node1.val = node2.val;
                node2.val = temp;
            }
            return;
        }
    }
    public void recoverTreeHelper(List<TreeNode> ansList,TreeNode root){
        if(root == null){
            return;
        }else {
            recoverTreeHelper(ansList,root.left);
            ansList.add(root);
            recoverTreeHelper(ansList,root.right);
        }
    }

    /*
        解法二：Morris 中序遍历
     */
    public void MorrisInorderTraversal(TreeNode root){
        if(root == null){
            return;
        }
        TreeNode current, pre;
        current = root;
        pre = root;
        while(current != null){
            if(current.left == null){
                System.out.println(current.val);
                current = current.right;
            }else {
                TreeNode rightmost = current.left;
                if(pre.right != current){
                    // find right most node, let current node become the right child of the right most node
                    while(rightmost.right != null){
                        rightmost = rightmost.right;
                    }
                    rightmost.right = current;
                    pre = current;
                    current = current.left;
                }else{
                    // restore the thread.
                    current = current.right;
                    pre.right = null;
                }
            }
        }
    }
}
